package com.dmall.play.interview.chapter08;

import java.util.*;

public class Leetcode47V2 {

    private List<List<Integer>> ans = null;
    private boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null) {
            return null;
        }
        ans = new ArrayList<>();
        visited = new boolean[nums.length];
        if (nums.length == 0) {
            return ans;
        }
        Arrays.sort(nums);
        Deque<Integer> stack = new ArrayDeque<>();
        findPermute(nums, 0, stack);
        return ans;
    }

    private void findPermute(int[] nums, int index, Deque<Integer> stack) {
        if (index == nums.length) {
            ans.add(new ArrayList<>(stack));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            stack.add(nums[i]);
            visited[i] = true;
            findPermute(nums, index + 1, stack);
            visited[i] = false;
            stack.removeLast();
        }
    }

    public static void main(String[] args) {
        Leetcode47V2 leetcode = new Leetcode47V2();
        int[] nums = {-1, 2, -1, 2, 1, -1, 2, 1};
        long start = System.currentTimeMillis();
        List<List<Integer>> res = leetcode.permuteUnique(nums);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        System.out.println(res.size());
        System.out.println(res);
    }
}
